Microcomputers, often referred to as PC's, have become ubiquitous. A very large number of the PC's now in use employ the Microsoft-Disk Operating System (hereinafter MS-DOS) operating system (published by Microsoft Corporation, Redmond, Wash.) or one that is virtually identical in operation to MS-DOS. The International Business Machines (hereinafter IBM) Personal Computer Model AT is one example of a PC that employs the MS-DOS operating system. Many application programs are written for MS-DOS PC's and their `clones`, which are sometimes collectively called `DOS machines`. These programs are written in reliance upon, and within the constraints of, the many standard features of DOS. Among these standard features are a utility for allocating a portion of the computer's memory space in response to a request made by the application program and a second utility for deallocating (or `freeing`) a previously allocated portion, again in response to a request from the application program.
As used herein, the following terms shall be understood as set forth below:
"memory space"--a plurality of sequentially addressed positions, each position corresponding to a basic unit of memory such as a byte or word; "segment"--a sequential portion, less than the whole, of a memory space; "memory block"--a segment which is defined by a fixed first end and second end, i.e. the lowest and highest addresses included in the block; "fragment"--a segment which can be either "allocated", i.e. assigned to an application, or "unallocated", i.e. available for assignment to an application; "size"--the number of addressed positions in a memory space or segment.
A program that is frequently encountered by designers of applications programs is memory fragmentation. FIGS. 1(a) and (b) are a schematic illustration of how memory fragmentation comes about.
It will be understood that a memory space may be viewed as a string of sequentially addressed positions, each position corresponding to a basic unit of memory, such as a byte. It will further be understood that the memory space may be considered to be occupied by a number of memory fragments, i.e. continuous blocks of sequentially addressed memory positions, and that each such fragment either has been allocated for the purpose of holding data (sometimes referred to as "in use") or is unallocated and hence available for allocation (sometimes referred to as "free" or "not in use"). In FIG. 1(a), reference numeral 10 indicates generally a box that may be considered to represent either the entire memory space of a computer, or a segment that is part of a memory space. It is assumed that memory portions, or fragments, 12, 14, 16 have been allocated, filling segment 10. In the DOS environment such an allocation can readily occur as an empty segment is allocated from beginning to end in response to a series of memory allocation requests. It will be noted that fragments 12 and 16 are approximately the same size and that fragment 14 is smaller than, and occupies the space between, fragments 12, 16. Now, if fragments 12, 16 are freed in response to deallocation requests, the status of segment 10 will be as shown in FIG. 1(b). At this point most of segment 10 is available for allocation. However, if the next requested memory allocation requires a fragment 18 that is only slightly larger than each of available fragments 12, 16, the requested fragment cannot be allocated in segment 10, even though the total available space in segment 10 greatly exceeds the size of the requested fragment.
As will be appreciated from the foregoing somewhat simplified example, memory fragmentation results in inefficient use of the memory space and also in what can be considered false indications that the memory space is exhausted. These conditions may become particularly acute for transaction-oriented or other applications in which the requested fragments vary in size over a considerable range and fragments are frequently deallocated. For these applications, a large number of relatively small unused fragments quickly builds up and it soon becomes impossible to fill requests for allocation of relatively large fragments, even though a substantial percentage of the memory space remains unused.
The usual solution to the false exhaustion of memory space is simply to run the application on a PC that has a larger memory capacity. Of course, the larger memory increases the cost of the PC, and the use of the memory remains inefficient.
Another known approach is coalescing, i.e. rearranging the allocated fragments so that unused portions of the memory space are combined. For example, and referring again to FIG. 1(b), this could take the form of moving fragment 14 to the top of segment 10 after fragments 12, 16 were freed, thereby combining fragments 12, 16. However, the software required for coalescing adds considerable complexity and may result in unacceptable overheads in terms of memory and processing time.